CMU 11642 的课程笔记。Exact match retrieval models 对专家来说很适用，它假定人能将需求描述为一个 boolean query，文档要么完全匹配要么完全不匹配，不匹配的文档分数就为 0。

Unranked Boolean Model

document score 为 1 或者 0，也就是匹配或者不匹配，没有匹配程度的分数，返回结果通常简单的按时间顺序排列。
很多系统在用，像 WestLaw, PubMed 等，因为它速度非常快，对一些问答系统来说，unranked boolean model 足够用了。

Ranked Boolean Model

为文档计算特定分数，文档 j 对 query $Q_{AND}(q_1…q_n)$ 的分数，一般取最小值。
$score(Q_{AND}(q_1…q_n),d_j) = MIN(score(q_1,d_j),score(q_n,d_j))$

文档 j 对 query $Q_{OR}(q_1…q_n)$ 的分数，一般计算 MEAN 或者 MAX，实践中 MEAN 比 MAX 更有效。
$score(Q_{OR}(q_1…q_n),d_j) = MAX(score(q_1,d_j),score(q_n,d_j))$
$score(Q_{OR}(q_1…q_n),d_j) = MEAN(score(q_1,d_j),score(q_n,d_j))$

优点：

效率高
可预测，可解释，结构化的查询语句
当用户非常清楚自己需要的是怎样的文档时非常有用
也可以用其它的 term weighting 方法

缺点：

仍然是完全匹配模型
很难在 Precision 和 Recall 间得到平衡
检索结果是按照文档有多么冗余的（redundantly）匹配 query 来排序的

Inverted list

Binary inverted lists

用于 unranked retrieval
Operators: AND, OR, AND-NOT, FIELD

Frequency inverted lists

用于 ranked retrieval
Operators: AND, OR, AND-NOT, FIELD, SUM, SYNONYM

Positional inverted lists

用于 ranked retrieval
Operators: AND, OR, AND-NOT, NEAR/n, SENTENCE/n, PASSAGE/n, WINDOW/n

Fixed-length inverted list

早期的搜索引擎会用，它的优点是

易于管理
bit-vector operations 速度快，并行化容易

然而…效率不高。
假定 inverted list 长度为 |C| bits (C 是 corpus 里的文档总数)，那么在某个 inverted list 里为 1 的 bits 的个数就是 df(多少篇文档出现了这个 term)，我们看 term with median tf 的 df，记作 $df_{median}$，观察一些语料可以发现，$|C|>>|df_{median}|$，(Wall Street Journal，|C|=174K, $df_{median}=2$)

Data structure

B tree(B+ tree, B* tree, etc)

$O(log n)$
易于扩展
可以用于完全匹配(exact-match lookup)，范围寻找(range lookup)，前缀寻找（prefix lookup）

Hash table

$O(1)$
不易于扩展
用于完全匹配(exact-match lookup)

Term dictionary

string –> integer，速度更快。

问题：多少存在内存，多少存在硬盘

frequent terms in RAM (eg.,ctf>=1,000)
less frequent terms to dis (eg.,ctf<1,000)

ctf < 1000，根据 Zipf’s law 算出 99.9% 的词可以存在硬盘。
${(A*N/1)-(A*N/1000) \over (A*N)}={999 \over 1000}=99.9%$